package sort.yht;

import sort.util.MySort;

/**
 * 功能描述：希尔排序
 * @Author: yht
 * @Date: 2021/8/11 14:12
 */
public class XiEr implements MySort {

  @Override
  public String getName() {
    return "【希尔排序】";
  }

  @Override
  public int[] sort(int[] a) {
//    return shell(a);
//    return shell2(a);
//    return shell3(a);
    return shell4(a);//3h+1
//    return myShell(a);
  }

  /**
   * 希尔排序
   * @param arr 要排序的数组
   */
  public int[] shell(int[] arr){
    //希尔排序实际上是直接插入排序的升级版本，在直接插入排序的算法中，如果越到后面突然出现某个比较小的值
    //这个时候排序的步骤就越长，希尔排序就是为了解决这个问题，先大致的排一下，然后拍的过程中用的是直接插入排序算法
    //首先计算步长
    for(int d = arr.length/2;d>0;d = d/2){
      //开始直接排序算法
      //先来一轮直接排序
      for(int i = d;i < arr.length;i++){
        //然后开始交换
        for(int j = i - d;j >=0; j = j-d){
          if(arr[j] > arr[j+d]){
            int temp = arr[j];
            arr[j] = arr[j+d];
            arr[j+d] = temp;
          }
        }
      }
    }
    return arr;
  }

  public int[] shell2(int[] num){
    for (int increment = num.length/2; increment > 0 ; increment=increment/2) {
      //根据增量对数组进行分组
      for (int i = increment; i < num.length; i++) {
        int index = i;
        //进行插入排序
        //注意：index-increment值的变化
        while ((index-increment)>=0&&num[index]<num[index-increment]){
          int temp = num[index];
          num[index] = num[index-increment];
          num[index-increment] = temp;
          index =index-increment;
        }
      }
    }
    return num;
  }

  public int[] shell3(int[] arr){
    int N = arr.length;
    //进行分组，最开始时的增量（gap）为数组长度的一半
    for(int  gap = N/2 ; gap > 0 ; gap/=2){
      //将各个分组进行插入排序
      for(int i = gap ; i<N ;i++){
        //将arr[i]插入到所在分组的正确位置上
        insert(arr,gap,i);
      }
    }
    return arr;
  }

  public int[] shell4(int[] array){
    int step = 1 ;
    int len = array.length;
    while(step <= len/3){
      step = step*3 + 1;//1,4,13,40......
    }
    while(step > 0){
      //分别对每个增量间隔进行排序
      for(int i = step ; i < len ; i++){
        int temp = array[i];
        int j = i;
        while(j > step-1 && temp <= array[j-step]){
          array[j] = array[j-step];
          j -= step;
        }
        array[j] = temp;
      }//end for
      step = (step-1)/3;
    }
    return array;
  }

  private void insert(int[] arr, int gap, int i) {
    int	inserted = arr[i];
    int j ;
    //插入的时候按组进行插入（组内元素两两相隔gap）
    for(j = i-gap ; j>=0  &&  inserted <arr[j] ; j-=gap){
      arr[j+gap] = arr[j];
    }
    arr[j+gap] = inserted;
  }

  /**
   * 我的希尔排序
   * @param a
   * @return
   */
  public int[] myShell(int[] a) {
    int size = a.length;
    for(int gap = size/2 ; gap > 0 ; gap/=2) {
      for(int m = gap ; m < size; m++) {
        int tmp = a[m];
        int j = 0;
        for(j = m-gap ; j >= 0 && tmp < a[j]; j-=gap) {
          a[j+gap] = a[j];
        }
        a[j+gap] = tmp;
      }
    }
    return a;
  }

  public static void main(String[] args) {
    new XiEr().testAll();
  }
}
